/* 
  希尔排序也叫递减增量排序，是插入排序的一种更高效的改进方法

  插入排序，是每次向前移动一位比较插入，
  希尔排序，给定一个步长，最后的步长回到1
*/

var sortArray = function (arr) {
  let len = arr.length;
  if (len <= 1) return arr;
  function swap(i, j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  let h = 1;
  while (h < len) {
      h = h * 3 + 1
  }
  while (h >= 1) {
      for (let i = h; i < len; i++) {
          for (let j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
              swap(j - h, j);
          }
      }

      h = Math.floor(h / 3);
  }
  return arr
};


console.log([]==![]); 